/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution
{
private:
    // 用数组模拟容易实现单调队列
    vector<TreeNode *> q1;
    vector<TreeNode *> q2;

public:
    int widthOfBinaryTree(TreeNode *root)
    {
        if (!root)
            return 0;
        q2.resize(10);
        q1.resize(10);
        // 也就是说null结点也是一段长度
        int ans = 1;
        int num = 1;
        q2[0] = root;
        int hh2 = 0, tt2 = 0;
        while (tt2 >= hh2)
        {
            int hh = 0, tt = -1;
            while (num--)
            {
                auto tmp = q2[hh2++];
                if (tt + 2 < q1.capacity())
                    q1.resize(q1.capacity() * 2);
                q1[++tt] = tmp ? tmp->left : nullptr;
                q1[++tt] = tmp ? tmp->right : nullptr;
            }
            // for(int i = hh; i <= tt; ++i) cout << (q[i] ? q[i]->val : 0) << ' ';
            // cout << endl;
            // 删去头空元素和尾空元素
            while (hh <= tt && !q1[hh])
                ++hh;
            while (hh <= tt && !q1[tt])
                --tt;
            // printf("tt:%d, num:%d\n",tt, tt - hh + 1);
            num = tt - hh + 1;
            hh2 = hh, tt2 = tt;
            ans = max(ans, num);
            q1.swap(q2);
            // cout << num << endl;
            // cout << ans << endl;
        }
        return ans;
    }
};